package leetcodev1.树;

import java.util.ArrayList;
import java.util.List;

public class LeetCode109 {

    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int size = list.size();
        return buildTree(list, 0, size - 1);
    }

    private TreeNode buildTree(List<Integer> list, int left, int right) {
        if (left > right) {
            return null;
        }

        if (left == right) {
            return new TreeNode(list.get(left));
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = buildTree(list, left, mid - 1);
        node.right = buildTree(list, mid + 1, right);
        return node;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
